package leetcode.editor.cn;
//[213]打家劫舍 II
public class HouseRobberIi213{
public static void main(String[] args) {

   int solution = new HouseRobberIi213().new Solution().rob(new int []{2,3,2});
   
}

  //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length < 1)return 0;
        if (nums.length == 1)return nums[0];
        if (nums.length == 2)return Math.max(nums[0],nums[1]);

        //steal 0
        int firstRob = rob(nums, 0, nums.length - 2);
        int lastRob = rob(nums, 1, nums.length - 1);

        return Math.max(firstRob,lastRob);
    }

    //start index, end index
      public int rob(int[] nums,int start,int end) {
//          if (nums == null || nums.length < 1 )return 0;
//          if (nums.length == 1 )return nums[0];
//          if (nums.length == 2 )return Math.max(nums[0],nums[1]);

          //0 not steal,  1 steal
          int dp[][] = new int[nums.length][2];
          dp[start][0] = 0;
          dp[start][1] = nums[start];
          for (int i = start +1; i <= end; i++) {
              dp[i][0] = Math.max(dp[i-1][0] ,dp[i-1][1]);
              dp[i][1] = dp[i-1][0] + nums[i];
          }

          return Math.max(dp[end][0],dp[end][1]);
      }
}
//leetcode submit region end(Prohibit modification and deletion)

}